package com.cx.algrithm.aleph;

/*
*
一是检验基础数据结构，二是确认程序语言的能力
题目:
给定一个有序整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]。

要求:
1.严格保证自己完成，不得参考网络答案。否则失去面试机会。
2.解题完成后，提供IDEA的截图。
3.给出解题思路、测试用例
4.时间复杂度要求O(n)。

* */
public class BothMatch {
//    // O(n^2)解决方法
//    public static void solve(int[] arr,int target){
//        System.out.println("target="+target);
//        for(int i=0;i<arr.length-1;i++){
//            for(int j=i+1;j<arr.length;j++){
//                if(arr[i]+arr[j]==target){
//                    System.out.println("["+i+","+j+"]");
//                }
//            }
//        }
//        System.out.println("----------------------------");
//    }
//    O(n)解决方法:利用递归提供内存空间

    public static void solve(int[] arr, int target) {
//        封装执行方法
        excute(arr, 0, target);
    }

    //    将数组，待比对的数组下标，目标sum作为变量
    public static void excute(int[] arr, int i, int target) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] == target) {
                System.out.println("[" + i + "," + j + "]");
            }
        }
        i++;
//        递归
        if (i < arr.length - 1) {
            excute(arr, i, target);
        }
    }

    //测试
    public static void main(String[] args) {
        int[] arr = {1, 2, 7, 8, 10, 11, 22, 28, 39};
        solve(arr, 10);

    }
}

